package src.CodeTop;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 * 示例 4：
 *
 *
 * 输入：root = [1,2]
 * 输出：[1,2]
 * 示例 5：
 *
 *
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 *
 */

public class _144BinaryTreePreorderTraversal {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.right = t2;
        t2.left = t3;
        List<Integer> list = preorderTraversal(t1);
        for (Integer i : list)
            System.out.println(i);
    }

    // 递归法
    public static List<Integer> preorderTraversal(TreeNode root) {
        // 存放结点的动态数组
        List<Integer> target = new ArrayList<>();
        preorder(root, target);
        return target;
    }

    public static void preorder(TreeNode root, List<Integer> target) {
        // 校验合法性
        if (root == null) {
            return;
        }
        // 前序遍历，根左右
        target.add(root.val);
        preorder(root.left, target);
        preorder(root.right, target);
    }
}
